

/**
 * @author Lukas Koell
 * @author David Medenjak
 * @author Johannes Riedmann
 */
public abstract class SortedTree extends StringTree {

    public SortedTree(StringTree parent, StringTree leftchild,
            StringTree rightchild, String key) {
        super(parent, leftchild, rightchild, key);
    }

    @Override
    public void add(String node) {
        SortedTree newTree = this.getNewInstance();

        newTree.leftchild = null;
        newTree.rightchild = null;
        newTree.label = node;
        newTree.parent = getPosition(this, node);

        if (node.compareTo(newTree.parent.label) < 0) {
            newTree.parent.leftchild = newTree;
        } else {
            newTree.parent.rightchild = newTree;
        }
    }

    /**
     * returns the position of node in currentTree
     * @param currentTree
     * @param node
     * @return
     */
    private SortedTree getPosition(SortedTree currentTree, String node) {
        SortedTree pos = null;

        if (node.compareTo(currentTree.label) < 0) {
            // if left child of current node is null, return current position
            if (currentTree.leftchild == null) {
                return (SortedTree) currentTree;
            } else {
                // else switch to the left child of current tree to continue
                // searching
                pos = getPosition((SortedTree) currentTree.leftchild, node);
            }
        } else if (node.compareTo(currentTree.label) >= 0) {
            // if right child of current node is null, return current position
            if (currentTree.rightchild == null) {
                return (SortedTree) currentTree;
            } else {
                // else switch to right child of current tree to continue
                // searching
                pos = getPosition((SortedTree) currentTree.rightchild, node);
            }
        }

        return pos;
    }

    @Override
    public String search(String node) {
        return "";
    }

    /**
     * if this tree is not the root, returns the tree that is highest in the hierarchy
     * @return
     */
    protected SortedTree findRoot() {
        SortedTree root = this;

        while (root.parent != null) {
            root = (SortedTree) root.parent;
        }
        return root;
    }
    
    /**
     * traverses through the tree, implementation depending on 
     * what type of sorted tree this is
     * @return the traversed tree as a string
     */
    public abstract String traverse();

    /**
     * gives back a new instance of the subclass
     * @return
     */
    public abstract SortedTree getNewInstance();
}
